package greedy;

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;

/**
 * @Author: 海琳琦
 * @Date: 2022/2/28 12:42
 * https://leetcode-cn.com/problems/queue-reconstruction-by-height/
 */
public class ReconstructQueue {

    /**
     *
     * @param people
     * @return
     */
    public static int[][] reconstructQueue(int[][] people) {
        //1、先排身高（从高到低）身高相同，k小的放前边
        Arrays.sort(people, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0]) {
                    return o1[1] - o2[1];
                }
                return o2[0] - o1[0];
            }
        });
        //2、按照k的大小从队列头开始插入
        LinkedList<int[]> list = new LinkedList<>();
        for (int i = 0; i < people.length; i++) {
            //前插法
            list.add(people[i][1], people[i]);
        }
        return list.toArray(new int[people.length][]);
    }

    public static void main(String[] args) {
        int[][] s = {{7,0},{4,4},{7,1},{5,0},{6,1},{5,2}};
        reconstructQueue(s);
    }
}
